package 力扣._25_K个一组翻转链表;


import 力扣.公用数据结构.ListNode;

public class Solution {

    //头插法逆转链表
    void reverse(ListNode pre, ListNode p, ListNode r) {
        ListNode t, p_p = p, p_r = r;
        pre.next = p_r.next;
        while (p_p != p_r) {
            t = p_p;
            p_p = p_p.next;
            t.next = pre.next;
            pre.next = t;
        }
        p_p.next = pre.next;
        pre.next = p_p;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        head = new ListNode(0, head);    //补上头结点
        //找到k个不为空的结点
        ListNode pre = head, l = head.next, r = head.next;
        while (true) {
            //将r指向这一组最后一个
            for (int i = 1; i < k; i++) {
                if (r == null)
                    break;
                r = r.next;
            }
            if (r == null)
                break;
            //逆转这一组
            reverse(pre, l, r);
            pre = l;
            l = pre.next;
            r = pre.next;
        }
        return head.next;
    }

    public static void main(String[] args) {

        ListNode node4 = new ListNode(4);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1, node2);
        ListNode listNode = new Solution().reverseKGroup(node1, 2);
        while (listNode != null) {
            System.out.print(listNode.val);
            listNode = listNode.next;
        }
    }
}
